package com.atwy.algorithm;

import java.util.Arrays;

/**
 * @Author: 小王子火
 * @Date: 2022/3/12
 * 动态规划：将大问题划分为小问题进行解决，从而一步步获取最优解；
 * 1、与分治算法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从子问题中解出原问题的解
 * 2、与分治算法不同的是，动态规划的求解的问题，经分解后得到的子问题往往不是相互独立的，下一个子阶段的求解是
 * 建立在上一个子阶段解的基础上，进行进一步求解。
 * 3、动态规划可以通过 “填表” 的方式来逐步推进，得到最优解
 *
 */
public class DynamicPrograming {
    public static void main(String[] args) {
        testBag_01();
    }

    /**
     * 0-1背包问题：
     * 有一个背包，容量是4kg，现有以下商品：
     * 吉他：1kg，1500元
     * 音响：4kg，3000元
     * 电脑: 3kg,2000元
     * 要求：
     * 1、装入背包的总价值最大，重量不超出；
     * 2、装入物品不重复
     *
     * 基本思路：
     * 1、构建题目信息：
     *      v[i]：第 i 个商品的价值。
     *      w[i]: 第 i 个商品的重量。
     *      C   : 背包容量。
     *      i 从0开始。
     * 2、构建背包容量与物品的表格，然后进行从左上往右下的填表流程，
     *   注意到最终求解的是总价值最大
     *      value[i][j]: j表示背包容量，二维数组的值表示最大的总价值，
     *      i 在这里可以理解为，解决第i个商品是否放入背包
     *      注：value[i-1][j],表示当前背包容量为j，处理了前i-1物品得出的最大价值
     *          而且这里就算给容量足够大，也没有放入第i物品，更严谨说是没考虑第i物品
     *          所以value[i-1][j] -> value[i][j],就是只需要去考虑，
     *          1、第i物品不放入背包得出最大价值，那这里的不放入其实就是不考虑也就是此时的value[i][j] = value[i-1][j]
     *          2、把第i物品放入背包得出最大价值，第i物品放入背包后，背包容量还剩 j-w[i],
     *             接下来就是去求解背包容量是j-w[i]时，有i-1个物品怎么得出最大价值的问题了
     *             而value[i-1][j-w[i]]就是这个含义
     *             所以第i物品放入背包后的最大价值就是 v[i] + value[i-1][j-w[i]]
     *
     *          第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定
     *
     *          3、比较1和2的结果，取最大就是value[i][j]的值
     *
     *
     * 3、这里只涉及整数
     */
    public static void testBag_01(){
        System.out.println("这是01背包问题--开始");
        // 数据初始化
        int[] v = {0,1500,3000,2000};
        int[] w = {0,1,4,3};
        int C = 4;
        // 物品的种类
        int nw = 4;
        // 背包的容量，从0-C
        int nc = C+1;
        int[][] value = new int[nw][nc];

        for (int i = 0; i < value.length; i++) {
            for (int j = 1; j < value[i].length; j++) {
                if(i==0){
                    value[i][j]=0;
                }else if(j<w[i]){
                    // 当前背包容量j < 当前第i物品的重量
                    // 取j容量时，处理第i-1物品时的最大价值
                    value[i][j] = value[i-1][j];
                }else if(j >= w[i]){
                    // 当前背包容量j >= 当前第i物品的重量
                    //
                    int temp = v[i] + value[i-1][j-w[i]];
                    if(value[i-1][j] > temp){
                        value[i][j] = value[i-1][j];
                    }else {
                        // 表示第i物品放入了背包中
                        value[i][j] = temp;
                    }

                }
            }
        }
        // 表格的最后一行最后一列的元素值就是本答案的解
        int result = value[nw-1][nc-1];

        System.out.println("得到的表格：");
        for (int i = 0; i < value.length; i++) {
            System.out.println(Arrays.toString(value[i]));
        }
        System.out.println("获取最优解的路径：");
        // 这种方式不能求出所有最优解
        int[] path = new int[nw];
        // 背包容量为C的最优解
        int weight = C;
        // 从表格的最后一格进行倒叙访问
        for(int i= nw-1;i>0;i--){
            if(value[i][weight] == value[i-1][weight]){
                // 说明表格的最优解取自前i-1的最优解
                path[i] = 0;
            }else {
                // 说明第i物品放入背包中了
                path[i] = 1;
                // 容量减去第i物品的重量，去求解i-1的最优解
                weight -= w[i];
            }
        }
        System.out.println("容量为"+C+"放入背包的的物品编号是:");
        for (int i = 0; i < path.length; i++) {
            if(path[i] == 1){
                System.out.print(i+"\t");
            }
        }
        System.out.println();
        System.out.println("最大总价值是："+result);
        System.out.println("这是01背包问题--结束");
    }
}
